1. Field of the Invention
The present invention generally relates to a string matching system and its method, and more particularly to the system and the method, which employ a plurality of Bloom filters for matching the strings and decide the shift distance of the search window to achieve the goal of accelerating hardware (HW) within sub-linear computation time.
2. Description of Related Art
While more and more people gain access to the Internet, there is ever-growing information flowing across the network. However, potential network intrusion and attack pose negative influences upon computer and network systems. For example, a variety of servers or even PCs (personal computers) are vulnerable to viruses.
In recent years, many safety-related information systems, such as a Network Intrusion Detection System (NIDS) and an antivirus system have become an important safety-related network technology, in which the matching efficiency of network packet content is decisive to the system performance. In the event of slow matching speed on strings, the network-dependent tasks may not be performed on time, so the failures of detecting network intrusion or viruses increases to a great extent. A sub-linear time algorithm can skip characters not in a match during scanning for signatures of intrusions and viruses. Therefore, it can be very efficient for signature matching. FIG. 1 depicts the flow process of a typical sub-linear time string matching method, of which the matching steps include:
Step S11: Start;
Step S12: Build up a block containing the last bytes in the search window, and look it up in the shift distance table to obtain a shift length N;
Step S13: Check if shift length is 0; if yes, perform Step S15, otherwise, perform Step S14;
Step S14: Shift forward the search window for the distance implied from the table lookup, and return to Step S12;
Step S15: Compare the hash value table that contains the pattern set;
Step S16: Check if a string in the table is the same; if yes, perform Step S17, otherwise, perform Step S18;
Step S17: Set the successful matching flag as true;
Step S18: Shift forward 1 byte for the sliding window, and return to Step S12; and
Step S19: Output.
The shift length of the search window is generally decided by means of looking up the shift distance table. This requires a large memory space to store the shift length for every block. When a small block is used to reduce the table space, frequent verification may be required, thus leading to slower matching speed and poorer matching efficiency. To overcome the aforementioned problems of the prior art, it would be an improvement if the art provides a better structure that can significantly improve the efficacy.
To this end, the inventor has provided the present invention of practicability after deliberate design and evaluation based on years of experience in the production, development and design of related products.